package leetcode

import kotlinetc.println

//https://leetcode.com/problems/unique-paths/

/**
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?
 */
fun main(args: Array<String>) {

    uniquePaths(7, 3).println()

}

//DP
/**
 每次计算前一列每个格子可以达到的可能，
 迭代计算下一列
 类似[uniquePathsWithObstacles]
 */
fun uniquePaths(m: Int, n: Int): Int {

    //C(m+n,n)

    val dp = Array(m + 1, { Array(n + 1, { 0 }) })


    for (i in 1 until m+1) {
        dp[i][1] = 1
    }

    for (i in 2 until n + 1) {//列
        for (j in 1 until m + 1) {
            var pathij = 0
            for (k in 1 until j + 1) {//到达当列的每一个格子的所有可能
                pathij += dp[k][i - 1]
            }
            dp[j][i] = pathij
        }
    }
    return dp[m][n]
}